#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <string>
#include <iostream>


// 构建部分匹配表
std::vector<int>build_next(const std::string& pattern)
{
	// 计算模式串初始化匹配表
	int n = pattern.size();
	std::vector<int>next(n, 0);

	//？？？
	int j = 0;
	for (int i = 1; i < n; i++)
	{
		while (j > 0 && pattern[i] != pattern[j])
		{
			j = next[j - 1];
		}
		// ???
		if (pattern[i] == pattern[j])
		{
			j++;
		}
		// ?????
		next[i] = j;
	}
	return next;
}
int kmp_find(const std::string& text, const std::string& pattern)
{
	// 难道真的无法突破这个难度缺口吗？？？？？？/
	// 预处理，让代码逻辑更清晰
	int n = text.size();
	int m = pattern.size();
	if (0 == m)	return 0;
	if (0 == n)	return -1;

	// ？？？
	std::vector<int>next = build_next(pattern);
	int j = 0;

	// 遍历一次挨个尝试我可以理解
	for (int i = 0; i < n; i++)
	{
		// ？？？？
		while (j > 0 && text[i] != pattern[j])
		{
			j = next[j - 1];
		}
		if (text[i] == pattern[j])
		{
			j++;
		}
		if (j == m)
		{
			return i - m + 1;
		}
	}
	return -1;
}
int main()
{
	std::string s = "abcabdabcabc";
	std::string p = "abcabc";

	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	std::cout << kmp_find(s, p) << std::endl;

	return 0;
}